/*
 * @lc app=leetcode.cn id=239 lang=java
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        // // 先声明return数组
        // int[] ret = new int[nums.length-k+1];

        // //这里用到了LinkedList，前面的接口Deque就是双端队列
        // Deque<Integer> deque = new LinkedList<>();

        // for (int i = 0; i < nums.length; i++) {

        //     // 这里就是主要逻辑，当前元素是否大于队尾元素，如果大于就删除
        //     while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
        //         deque.removeLast();
        //     }

        //     // 如果不大于，或者队列为空了，则加入下标
        //     deque.addLast(i);

        //     // 这里就是判断，两个下标差是否等于k，如果等于就删除头部
        //     if (i-deque.getFirst() == k){
        //         deque.removeFirst();
        //     }

        //     // 这里说明什么时候将队列头加入return数组
        //     if (i-k+1 >=0){
        //         ret[i-k+1] = nums[deque.getFirst()];
        //     }
        // }
        // return ret;

        if(nums.length < 2 || nums == null ) {
            return nums;
        }

        LinkedList<Integer> queue = new LinkedList<>();

        int[] res = new int[nums.length - k + 1];
        for(int i = 0; i < nums.length; i++) {
            while(!queue.isEmpty() && queue.peekLast() <= nums[i]) {
                queue.pollLast();
            }

            queue.addLast(i);

            if(queue.peek() <= i-k) {
                queue.poll();
            }

            if(i + 1 >= k) {
                res[i + 1 - k] = nums[queue.peek()];
            }
        }
        return res;
    }

}
// @lc code=end

